本篇主要為記錄參加學校資訊班的作業，相關思考難點的紀錄。
題目為比較4種sort演算法(Array-Sort、Insertion-Sort、Selection-Sort、Bubble-Sort)的執行速度，考慮不同排列會有不同的時間，本次設計取3次時間的平均值。

思考點：

1. 先理解Insertion-Sort、Selection-Sort、Bubble-Sortsort的運作方式，並拆解後呈現出來。
2. 計算運算的時間並同時呈現進度條。
3. 優化，本篇很明顯在描述4種排列法的時間計算時，幾乎要用上3層迴圈了QQ，只是沒寫出來。

import java.util.Arrays;

public class PerformanceBenchmarkforSortingAlgorithms {

	public static void main(String[] args) {

		int size[] = { 1000, 2000, 4000, 8000, 16000, 32000, 64000 };
		System.out.print("Simulating ArraySort：");
		double[] Amin = new double[size.length];
		for (int times = 0; times < size.length; times++) {

			int[] test = new int[size[times]];
			double[] result = new double[3];	          //同樣的資料數量，算3次		
			for (int i = 0; i < 3; i++) {
				test = sample(test);                      //reset資料變回亂數
				double A000 = System.nanoTime()/1e6 ;
				ArraySort(test);                          // 呼叫method-ArraySort
				double A001 = System.nanoTime()/1e6 ;
				result[i] = (A001 - A000);                //將每一次的時間存起來
			}
			;

			System.out.printf("．");                       //顯示執行進度
			Amin[times] = (result[0] + result[1] + result[2])/3;   //3次平均

		}
		;
		System.out.println("done");

		System.out.print("Simulating InsertionSort：");
		
		double[] Imin = new double[size.length];
		for (int times = 0; times < size.length; times++) {

			int[] test = new int[size[times]];
			double[] result = new double[3];			
			for (int i = 0; i < 3; i++) {
				test = sample(test);
				double I000 = System.nanoTime()/1e6;
				InsertionSort(test);                    // 呼叫method-InsertionSort
				double I001 = System.nanoTime()/1e6;
				result[i] = (I001 - I000);
			}
			;

			System.out.printf("．");
			Imin[times] = (result[0] / 3 + result[1] / 3 + result[2] / 3);

		}
		;
		System.out.println("done");

		System.out.print("Simulating SelectionSort：");
		double[] Smin = new double[size.length];
		for (int times = 0; times < size.length; times++) {

			int[] test = new int[size[times]];
			double[] result = new double[3];			
			for (int i = 0; i < 3; i++) {
				test = sample(test);
				double I000 = System.nanoTime()/1e6;
				SelectionSort(test);                  // 呼叫method-SelectionSort
				double I001 = System.nanoTime()/1e6;
				result[i] = (I001 - I000);
			}
			;

			System.out.printf("．");
			Smin[times] = (result[0] / 3 + result[1] / 3 + result[2] / 3);

		}
		;
		System.out.println("done");

		System.out.print("Simulating BubbleSort：");

		double[] Bmin = new double[size.length];
		for (int times = 0; times < size.length; times++) {

			int[] test = new int[size[times]];
			double[] result = new double[3];			
			for (int i = 0; i < 3; i++) {
				test = sample(test);
				double I000 = System.nanoTime()/1e6;
				BubbleSort(test);                       // 呼叫method-BubbleSort
				double I001 = System.nanoTime()/1e6;
				result[i] = (I001 - I000);
			}
			;

			System.out.printf("．");
			Bmin[times] = (result[0] / 3 + result[1] / 3 + result[2] / 3);

		}
		;
		System.out.println("done");
		System.out.println("Benchmark (time unit: ms)");
		System.out.printf("%5s%23s%20s%20s%19s", "size", "BubbleSort", "SelectionSort", "InsertionSort", "ArraySort");
		System.out.println();

		for (int i = 0; i < size.length; i++) {
			System.out.printf("%5d%20.3f%20.3f%20.3f%20.3f", size[i], (double) Bmin[i], (double) Smin[i],
					(double) Imin[i], (double) Amin[i]);
			System.out.println();
		}

	}

	public static int[] sample(int[] num) {                //生成亂數的排列
		int[] a = num;
		for (int i = 0; i < a.length; i++) {
			a[i] = i;
		}
		;
		for (int i = 0; i < a.length; i++) {
			int j = (int) (Math.random() * (a.length - i) + i);
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
		;
		return a;

	}

	public static int[] ArraySort(int[] array01) {
		int[] A = array01;
		Arrays.sort(A);
		return A;
	}

	public static int[] BubbleSort(int[] array01) {
		int[] A = array01;
		boolean swapped;
		do {
			swapped = false;
			for (int i = 0; i < A.length - 1; i++) {
				if (A[i] > A[i + 1]) {
					int temp = A[i];
					A[i] = A[i + 1];
					A[i + 1] = temp;
					swapped = true;
				}
				;

			}
			;
		} while (swapped);

		return A;
	}

	public static int[] SelectionSort(int[] array01) {
		int[] A = array01;
		for (int j = 0; j < A.length; j++) {
			int min = j;
			for (int i = 0; i < A.length; i++) {
				if (A[min] > A[i]) {
					min = i;
				}
				;
				int temp;
				temp = A[j];
				A[j] = A[min];
				A[min] = temp;
			}
			;
		}
		;
		return A;
	}

	public static int[] InsertionSort(int[] array01) {
		int[] A = array01;

		for (int i = 0; i < A.length; i++) {
			int index = i;
			while (index > 0 && A[index - 1] >= A[index]) {
				int tmp = A[index - 1];
				A[index - 1] = A[index];
				A[index] = tmp;
				index -= 1;       //繼續向左邊比大小；當index為0的時候，代表已經排到最小了，loop停止
			}
		}
		return A;
	}
}

參考文章：

1. Comparison Sort: Insertion Sort(插入排序法)：http://alrightchiu.github.io/SecondRound/comparison-sort-insertion-sortcha-ru-pai-xu-fa.html